package pers.qianyu.month_202012.date_20201219;

import java.util.*;

/**
 * 241. 为运算表达式设计优先级
 * https://leetcode-cn.com/problems/different-ways-to-add-parentheses/
 *
 * @author mizzle rain
 * @date 2020-12-19 20:09
 */
public class DiffWaysToCompute {
    public List<Integer> diffWaysToCompute(String input) {
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            char ch = input.charAt(i);
            if (ch == '+' || ch == '-' || ch == '*') {
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));
                for (Integer i1 : left) {
                    for (Integer i2 : right) {
                        if (ch == '+') {
                            res.add(i1 + i2);
                        } else if (ch == '-') {
                            res.add(i1 - i2);
                        } else {
                            res.add(i1 * i2);
                        }
                    }
                }
            }
        }
        if (res.isEmpty()) {
            res.add(Integer.parseInt(input));
        }
        return res;
    }
}
